<!DOCTYPE html>
<html CN>







<head>
	
	
	<link rel="stylesheet" href="/css/allinone.min.css"> 

	
	<!-- Global Site Tag (gtag.js) - Google Analytics -->
	<script async src="https://www.googletagmanager.com/gtag/js?id=UA-42863699-1"></script>
	<script>
		window.dataLayer = window.dataLayer || [];
		function gtag(){dataLayer.push(arguments);}
		gtag('js', new Date());
		gtag('config', 'UA-42863699-1');
	</script>
	

	<meta charset="utf-8" />
	<meta http-equiv="X-UA-Compatible" content="IE=edge" />

	<title>raft 一致性算法 | Cizixs Write Here</title>

	<meta name="HandheldFriendly" content="True" />
	<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
	<meta name="generator" content="hexo">
	<meta name="author" content="Cizixs Wu">
	<meta name="description" content="">

	
	<meta name="keywords" content="">
	

	
	<link rel="shortcut icon" href="https://cizixs-blog.oss-cn-beijing.aliyuncs.com/006tNc79ly1g1qxfovpzyj30740743yg.jpg">
	

	
	<meta name="theme-color" content="#3c484e">
	<meta name="msapplication-TileColor" content="#3c484e">
	

	

	

	<meta property="og:site_name" content="Cizixs Write Here">
	<meta property="og:type" content="article">
	<meta property="og:title" content="raft 一致性算法 | Cizixs Write Here">
	<meta property="og:description" content="">
	<meta property="og:url" content="http://cizixs.com/2017/12/04/raft-consensus-algorithm/">

	
	<meta property="article:published_time" content="2017-12-04T00:12:00+08:00"/> 
	<meta property="article:author" content="Cizixs Wu">
	<meta property="article:published_first" content="Cizixs Write Here, /2017/12/04/raft-consensus-algorithm/" />
	

	
	
	<script src="https://cdn.staticfile.org/jquery/3.2.1/jquery.min.js"></script>
	

	
	<script src="https://cdn.staticfile.org/highlight.js/9.10.0/highlight.min.js"></script>
	

	
	
<link rel="stylesheet" href="/css/prism-base16-ateliersulphurpool.light.css" type="text/css"></head>
<body class="post-template">
    <div class="site-wrapper">
        




<header class="site-header outer" style="z-index: 999">
    <div class="inner">
        
<nav class="site-nav"> 
    <div class="site-nav-left">
        <ul class="nav">
            <li>
                
                <a href="/" title="Home">Home</a>
                
            </li>
            
            
            <li>
                <a href="/about" title="About">About</a>
            </li>
            
            <li>
                <a href="/archives" title="Archives">Archives</a>
            </li>
            
            
        </ul> 
    </div>
    <div class="site-nav-right">
        
<div class="social-links" >
    
    <a class="social-link" title="weibo" href="https://weibo.com/1921727853" target="_blank" rel="noopener">
        <svg viewBox="0 0 1141 1024" xmlns="http://www.w3.org/2000/svg"><path d="M916.48 518.144q27.648 21.504 38.912 51.712t9.216 62.976-14.336 65.536-31.744 59.392q-34.816 48.128-78.848 81.92t-91.136 56.32-94.72 35.328-89.6 18.944-75.264 7.68-51.712 1.536-49.152-2.56-68.096-10.24-78.336-21.504-79.872-36.352-74.24-55.296-59.904-78.848q-16.384-29.696-22.016-63.488t-5.632-86.016q0-22.528 7.68-51.2t27.136-63.488 53.248-75.776 86.016-90.112q51.2-48.128 105.984-85.504t117.248-57.856q28.672-10.24 63.488-11.264t57.344 11.264q10.24 11.264 19.456 23.04t12.288 29.184q3.072 14.336 0.512 27.648t-5.632 26.624-5.12 25.6 2.048 22.528q17.408 2.048 33.792-1.536t31.744-9.216 31.232-11.776 33.28-9.216q27.648-5.12 54.784-4.608t49.152 7.68 36.352 22.016 17.408 38.4q2.048 14.336-2.048 26.624t-8.704 23.04-7.168 22.016 1.536 23.552q3.072 7.168 14.848 13.312t27.136 12.288 32.256 13.312 29.184 16.384zM658.432 836.608q26.624-16.384 53.76-45.056t44.032-64 18.944-75.776-20.48-81.408q-19.456-33.792-47.616-57.344t-62.976-37.376-74.24-19.968-80.384-6.144q-78.848 0-139.776 16.384t-105.472 43.008-72.192 60.416-38.912 68.608q-11.264 33.792-6.656 67.072t20.992 62.976 42.496 53.248 57.856 37.888q58.368 25.6 119.296 32.256t116.224 0.512 100.864-21.504 74.24-33.792zM524.288 513.024q20.48 8.192 38.912 18.432t32.768 27.648q10.24 12.288 17.92 30.72t10.752 39.424 1.536 42.496-9.728 38.912q-8.192 18.432-19.968 37.376t-28.672 35.328-40.448 29.184-57.344 18.944q-61.44 11.264-117.76-11.264t-88.064-74.752q-12.288-39.936-13.312-70.656t16.384-66.56q13.312-27.648 40.448-51.712t62.464-38.912 75.264-17.408 78.848 12.8zM361.472 764.928q37.888 3.072 57.856-18.432t21.504-48.128-15.36-47.616-52.736-16.896q-27.648 3.072-43.008 23.552t-17.408 43.52 9.728 42.496 39.424 21.504zM780.288 6.144q74.752 0 139.776 19.968t113.664 57.856 76.288 92.16 27.648 122.88q0 33.792-16.384 50.688t-35.328 17.408-35.328-14.336-16.384-45.568q0-40.96-22.528-77.824t-59.392-64.512-84.48-43.52-96.768-15.872q-31.744 0-47.104-15.36t-14.336-34.304 18.944-34.304 51.712-15.36zM780.288 169.984q95.232 0 144.384 48.64t49.152 146.944q0 30.72-10.24 43.52t-22.528 11.264-22.528-14.848-10.24-35.84q0-60.416-34.816-96.256t-93.184-35.84q-19.456 0-28.672-10.752t-9.216-23.04 9.728-23.04 28.16-10.752z" /></svg>
    </a>
    

    
    <a class="social-link" title="github" href="https://github.com/cizixs" target="_blank" rel="noopener">
        <svg viewBox="0 0 1049 1024" xmlns="http://www.w3.org/2000/svg"><path d="M524.979332 0C234.676191 0 0 234.676191 0 524.979332c0 232.068678 150.366597 428.501342 358.967656 498.035028 26.075132 5.215026 35.636014-11.299224 35.636014-25.205961 0-12.168395-0.869171-53.888607-0.869171-97.347161-146.020741 31.290159-176.441729-62.580318-176.441729-62.580318-23.467619-60.841976-58.234462-76.487055-58.234463-76.487055-47.804409-32.15933 3.476684-32.15933 3.476685-32.15933 53.019436 3.476684 80.83291 53.888607 80.83291 53.888607 46.935238 79.963739 122.553122 57.365291 152.97411 43.458554 4.345855-33.897672 18.252593-57.365291 33.028501-70.402857-116.468925-12.168395-239.022047-57.365291-239.022047-259.012982 0-57.365291 20.860106-104.300529 53.888607-140.805715-5.215026-13.037566-23.467619-66.926173 5.215027-139.067372 0 0 44.327725-13.906737 144.282399 53.888607 41.720212-11.299224 86.917108-17.383422 131.244833-17.383422s89.524621 6.084198 131.244833 17.383422C756.178839 203.386032 800.506564 217.29277 800.506564 217.29277c28.682646 72.1412 10.430053 126.029806 5.215026 139.067372 33.897672 36.505185 53.888607 83.440424 53.888607 140.805715 0 201.64769-122.553122 245.975415-239.891218 259.012982 19.121764 16.514251 35.636014 47.804409 35.636015 97.347161 0 70.402857-0.869171 126.898978-0.869172 144.282399 0 13.906737 9.560882 30.420988 35.636015 25.205961 208.601059-69.533686 358.967656-265.96635 358.967655-498.035028C1049.958663 234.676191 814.413301 0 524.979332 0z" /></svg>
    </a>
    

    
    <a class="social-link" title="stackoverflow" href="https://stackoverflow.com/users/1925083/cizixs" target="_blank" rel="noopener">
        <svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24"><path d="M15 21h-10v-2h10v2zm6-11.665l-1.621-9.335-1.993.346 1.62 9.335 1.994-.346zm-5.964 6.937l-9.746-.975-.186 2.016 9.755.879.177-1.92zm.538-2.587l-9.276-2.608-.526 1.954 9.306 2.5.496-1.846zm1.204-2.413l-8.297-4.864-1.029 1.743 8.298 4.865 1.028-1.744zm1.866-1.467l-5.339-7.829-1.672 1.14 5.339 7.829 1.672-1.14zm-2.644 4.195v8h-12v-8h-2v10h16v-10h-2z"/></svg>
    </a>
    

    

    
    <a class="social-link" title="twitter" href="https://twitter.com/cizixs" target="_blank" rel="noopener">
        <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 32 32"><path d="M30.063 7.313c-.813 1.125-1.75 2.125-2.875 2.938v.75c0 1.563-.188 3.125-.688 4.625a15.088 15.088 0 0 1-2.063 4.438c-.875 1.438-2 2.688-3.25 3.813a15.015 15.015 0 0 1-4.625 2.563c-1.813.688-3.75 1-5.75 1-3.25 0-6.188-.875-8.875-2.625.438.063.875.125 1.375.125 2.688 0 5.063-.875 7.188-2.5-1.25 0-2.375-.375-3.375-1.125s-1.688-1.688-2.063-2.875c.438.063.813.125 1.125.125.5 0 1-.063 1.5-.25-1.313-.25-2.438-.938-3.313-1.938a5.673 5.673 0 0 1-1.313-3.688v-.063c.813.438 1.688.688 2.625.688a5.228 5.228 0 0 1-1.875-2c-.5-.875-.688-1.813-.688-2.75 0-1.063.25-2.063.75-2.938 1.438 1.75 3.188 3.188 5.25 4.25s4.313 1.688 6.688 1.813a5.579 5.579 0 0 1 1.5-5.438c1.125-1.125 2.5-1.688 4.125-1.688s3.063.625 4.188 1.813a11.48 11.48 0 0 0 3.688-1.375c-.438 1.375-1.313 2.438-2.563 3.188 1.125-.125 2.188-.438 3.313-.875z"/></svg>

    </a>
    

    
    <a class="social-link" title="instagram" href="https://www.instagram.com/cizixs/" target="_blank" rel="noopener">
        <svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24"><path d="M12 2.163c3.204 0 3.584.012 4.85.07 3.252.148 4.771 1.691 4.919 4.919.058 1.265.069 1.645.069 4.849 0 3.205-.012 3.584-.069 4.849-.149 3.225-1.664 4.771-4.919 4.919-1.266.058-1.644.07-4.85.07-3.204 0-3.584-.012-4.849-.07-3.26-.149-4.771-1.699-4.919-4.92-.058-1.265-.07-1.644-.07-4.849 0-3.204.013-3.583.07-4.849.149-3.227 1.664-4.771 4.919-4.919 1.266-.057 1.645-.069 4.849-.069zm0-2.163c-3.259 0-3.667.014-4.947.072-4.358.2-6.78 2.618-6.98 6.98-.059 1.281-.073 1.689-.073 4.948 0 3.259.014 3.668.072 4.948.2 4.358 2.618 6.78 6.98 6.98 1.281.058 1.689.072 4.948.072 3.259 0 3.668-.014 4.948-.072 4.354-.2 6.782-2.618 6.979-6.98.059-1.28.073-1.689.073-4.948 0-3.259-.014-3.667-.072-4.947-.196-4.354-2.617-6.78-6.979-6.98-1.281-.059-1.69-.073-4.949-.073zm0 5.838c-3.403 0-6.162 2.759-6.162 6.162s2.759 6.163 6.162 6.163 6.162-2.759 6.162-6.163c0-3.403-2.759-6.162-6.162-6.162zm0 10.162c-2.209 0-4-1.79-4-4 0-2.209 1.791-4 4-4s4 1.791 4 4c0 2.21-1.791 4-4 4zm6.406-11.845c-.796 0-1.441.645-1.441 1.44s.645 1.44 1.441 1.44c.795 0 1.439-.645 1.439-1.44s-.644-1.44-1.439-1.44z"/></svg>
    </a>
    
    
    
</div>
    </div>
</nav>
    </div>
</header>


<main id="site-main" class="site-main outer" role="main">
    <div class="inner">
        <header class="post-full-header">
            <section class="post-full-meta">
                <time  class="post-full-meta-date" datetime="2017-12-03T16:00:00.000Z" itemprop="datePublished">
                    2017-12-4
                </time>
                
                <span class="date-divider">/</span>
                
                <a href="/categories/blog/">blog</a>&nbsp;&nbsp;
                
                
            </section>
            <h1 class="post-full-title">raft 一致性算法</h1>
        </header>
        <article class="post-full no-image">
            
            <section class="post-full-content">
                <div id="lightgallery" class="markdown-body">
                    <h2 id="分布式系统和一致性"><a href="#分布式系统和一致性" class="headerlink" title="分布式系统和一致性"></a>分布式系统和一致性</h2><p>分布式系统有一个很重要的问题要解决，当一台机器出现问题时，我们希望整个集群还是能够正常运行的，以达到高可用的要求。因为系统的数据是不断变化的，所以要保证集群的数据是同步的，不然会出现数据混论或者丢失的情况。这就是<strong>一致性问题。</strong></p>
<p>换个说法，一致性就是让多台机器对一组给定的操作最终得到的状态一样，也就是所有机器执行命令的顺序是一样的，对客户端来说，它们表现得就要像一个机器一样。</p>
<p>分布式一致性问题可以抽象成下面这张图(分布式状态机 Replicated State Machine)：</p>
<p><img src="https://cizixs-blog.oss-cn-beijing.aliyuncs.com/006tNc79gy1fm3p3e0lnnj30sh09zwhg.jpg" alt=""></p>
<p>最终的目的是所有节点上保存的状态机器（文件内容）是一样的，这是通过各个节点上一致性模块之间的通信完成的，它们保证按顺序添加日志，然后把日志执行修改状态机的内容。如果机器初始状态相同，而且日志中记录顺序是一样的，那么最终的状态一定也是相同的。</p>
<p>一致性算法需要满足以下条件才能在实际系统中工作：</p>
<ul>
<li>安全（safety）：不会返回错误的结果，即使网络出现延迟、分割（partitions）、丢包、重复和乱序</li>
<li>可用（available）：只要有一半以上的机器正常工作（能够互相通信并且可以和客户端通信），整个集群就要能正常工作</li>
<li>不能通过时间来保证一致性，错误的时钟以及严重的消息延迟最多只能造成集群不可用</li>
<li>只要大部分机器完成命令的执行，这个命令就算完成，结果可以返回给客户端。而不用等到那些执行更慢的少数节点完成，它们的操作可以异步在后台运行</li>
</ul>
<p>分布式系统关于一致性最著名的算法是 paxos，它的发布者 Lamport 是图灵奖的获得者。但是 paxos 算法非常复杂，很多实现都是它的特殊版。尽管 Lamport 后来还发布过 Paxos Made Simple 的文章，试图用更简单的语言解释 paxos 算法，但是这个版本的解释还是过于复杂，这对于理解和实现都带来困难。</p>
<p>paxos 算法在分布式系统中地位很高，Chubby 作者有过这样一段话：</p>
<blockquote>
<p>There is only one consensus protocol, and that’s Paxos. All other approaches are just broken versions of Paxos.</p>
</blockquote>
<p>只有一种一致性算法，那就是 Paxos；而其他所有的一致性算法都是 Paxos 的特殊版本。</p>
<p>raft 算法是基于 paxos 算法提出来的，主要是为了更加易懂，提出 raft 算法的论文是 《In search of an Understandable Consensus Algorithm》，可以在网上很容易搜到原文。</p>
<h2 id="raft-算法"><a href="#raft-算法" class="headerlink" title="raft 算法"></a>raft 算法</h2><p>为了容易理解，raft 算法主要分成几个可以单独解释的问题：</p>
<ul>
<li>Leader election：主节点选举，从集群中所有节点中选择一个作为主节点</li>
<li>Log replication：日志复制，主节点全权负责和客户端的交互，以及日志复制到其他节点，保证日志的一致性</li>
<li>Safety：安全，如果一个节点往保存的状态添加一个日志记录，其他节点不会再同一个日志 index 时期添加一个不同的记录</li>
</ul>
<p>它的工作流程是这样的：集群选择出一个节点作为 leader，leader 节点负责接收客户端的请求（日志），并负责把请求复制给所有的从节点，保证节点之间数据的同步。如果 leader 节点出现问题挂掉，那么其他正常节点会重新选择 leader。</p>
<h3 id="选主-leader-election"><a href="#选主-leader-election" class="headerlink" title="选主 leader election"></a>选主 leader election</h3><p>每个节点在任意情况下，只能有三种状态可选：</p>
<ul>
<li>leader：领导节点，或者主节点，用来处理客户端发来的请求，并保证请求数据在整个集群的同步，需要用心跳和 follower 节点通信，通知它们自己的可用性</li>
<li>follower：负责处理 leader 和 candidate 请求的节点。如果客户端把请求发送给 follower 节点，它需要把请求转发给 leader，由 leader 统一负责管理</li>
<li>candidate：leader 的候选人，只是在选举过程中短暂出现的状态。如果通过选举，则会变成 leader；如果选举失败，还是会回到 follower 状态</li>
</ul>
<p><img src="https://cizixs-blog.oss-cn-beijing.aliyuncs.com/006tNc79gy1fm40vgcvazj30y20j6tap.jpg" alt=""></p>
<p>raft 算法还有一个任期（Term）的概念，任期是依次递增的编号，每次选举都是一个新的任期。<strong>在一个任期内最多只能有一个 leader</strong>，也就是说一个任期可以有一个 leader，表示正常工作；也可以没有 leader，表明选举失败。某个节点选举成功后，就成为当前任期的 leader，负责日志复制工作。</p>
<p>任期的主要目的是保证所有节点逻辑时间上的一致，而不会出现过期的请求导致逻辑混乱的情况。</p>
<p><img src="https://cizixs-blog.oss-cn-beijing.aliyuncs.com/006tNc79gy1fm40vu4bbij30ya0e9q3f.jpg" alt=""></p>
<p>每个节点都会保存一个当前任期的值，当节点通信时会交互当前任期的值，如果节点发现其他节点的当前任期比自己的大，就更新自己当前任期的值；如果 leader 节点发现有比自己大的任期值，则知道自己的任期过期了，集群中有更新的 leader 节点，它立即变成 follower 状态；如果节点接收到历史任期的请求，则直接无视（这很可能是因为网络延迟或者报文重复导致的）。</p>
<p>当节点刚启动的时候，默认是在 follower 状态。如果它能定时收到 leader 的心跳或者日志复制的请求，则会一直处于该状态；如果在设定的超时时间（election timeout）内没有收到 leader 的消息，则认为当前集群没有 leader，或者 leader 以及失效，立即会发起重新投票。</p>
<p>投票开始，节点会增加自己的当前任期值，转换成 candidate 状态，并向其他节点发送请求投票的消息（表示自己想成为下一个任期的 leader）。下面的状态分为三种情况：</p>
<ol>
<li>节点收到大多数节点的投票，成为新任期的 leader。每个节点在每个任期只能投票一次，采取先到先得的原则，投票给最先收到的选主节点。大多数原则保证一个任期最多只能有一个节点</li>
<li>节点发现已经有另一个节点成为 leader。在等待选举结果的时候，节点收到了心跳或者日志复制的消息（也就是有 leader 了），如果这个 leader 合法（任期比自己的当前任期高），则当前节点会自动变成 follower 状态；否则会继续等待</li>
<li>一段时间过去，并没有任何节点成为 leader。比如有多个节点要选举 leader，而且都投票结果比较分散，没有节点获得过半的票数</li>
</ol>
<p>如果不采取任何措施，那么第三种情况一直出现，会导致整个集群一直处于选举的状态，这当然是不可接受的。为此，raft 采取了随机时间的办法。</p>
<p>首先，选举超时时间（election timeout）是随机的，保证会有一个节点首先超时，率先选举，其他节点来不及和它竞选，它就会成为新的 leader，发送心跳和日志复制请求。</p>
<p>其次，在开始选举时，每个 candidate 节点重置它的超时计时器，等待计时器结束之后才会开始下一次选举，从而打乱下次选举的前后顺序，保证有一个节点先开始选举，并成为 leader。</p>
<p>事实证明，这两种方式能够保证选举在很短的时间里完成，而不会一直循环。</p>
<p><strong>NOTE:</strong></p>
<ol>
<li>选举过期时间（election timeout）一般设置为 150-300ms，这是大量实验得到的经验值</li>
</ol>
<h3 id="日志复制-Log-replication"><a href="#日志复制-Log-replication" class="headerlink" title="日志复制 Log replication"></a>日志复制 Log replication</h3><p>当一个节点成为 leader 之后，它就会负责接收客户端的请求。客户端的每个请求都是一个指令，replicate state machine（复制状态机） 会执行这个指令，修改自己的状态。</p>
<p>主节点收到请求之后，把它作为新纪录写入到自己的日志中，然后发送请求给所有的从节点，让它们进行日志复制，等到日志复制完成，leader 节点返回结果给客户端。如果有从节点失败或者比较慢，主节点会一直重试，直到所有的节点保存了所有的日志记录（达到统一的状态）。</p>
<p>每个日志记录都要保存一个状态机的指令，同时还保存主节点接受请求时候的任期值，此外还有一个 index 表示它在日志文件中的位置。</p>
<p>当日志记录被状态机执行后，就称它为已提交（commited）。当主节点知道日志记录已经复制到大多数节点时，会把当前记录提交到本地的状态机（因为日志已经更新到大多数节点，所有数据是安全的），也就是更改数据的值。</p>
<p>leader 节点会记录已经提交（commited）的最大日志 index，然后后续的心跳和日志复制请求会带上这个值，这样从节点就能知道哪些记录已经提交了，自己也会让状态机开始执行日志中的记录。从而达到所有状态机数据的一致性！</p>
<p>这样的日志机制保证了如果不同节点的日志文件某个记录的 index 和任期都相同，那么它们的内容也一定相同，而且之前的日志记录也一定是一样的。</p>
<p>当主节点发送日志复制的请求时，它会带上前一个日志记录的 index 和 term，如果从节点发现自己的日志中不存在这个记录，则会拒绝这个请求。</p>
<p><img src="https://cizixs-blog.oss-cn-beijing.aliyuncs.com/006tNc79gy1fm40wfjblhj30ym0i5dif.jpg" alt=""></p>
<p>正常情况下，每次日志复制都能正常完成，而且节点都能保证日志记录都是完全一致的。但如果 leader 节点崩溃掉，可能会出现日志不一致的情况（奔溃的主节点还没有完全把自己日志文件中的记录复制到其他节点，因此有些节点的日志比另外一些节点内容更多）。</p>
<p>对于日志内容不一致的请求，raft 采取用主节点日志内容覆盖 follower 节点日志的做法，先找到从节点日志和自己日志记录第一个不一致的地方，然后一直覆盖到最后。</p>
<p>整个过程是这样的：当某个节点当选 leader 之后，会发送日志复制请求到从节点，并带着 nextIndex（主节点要发送的下一个日志记录的 index），如果从节点出现日志记录不一致的情况，会拒绝该请求，那么主节点知道发生了不一致，递减 nextIndex，然后重新发送请求，直到日志一致的地方，一切回复正常，然后继续发送日志复制请求，就会把从节点的日志覆盖为主节点的日志内容。</p>
<h3 id="安全-safety"><a href="#安全-safety" class="headerlink" title="安全 safety"></a>安全 safety</h3><p>前面提到的选主和日志复制是 raft 算法的核心，能够保证日志里面记录最终是一致的，但是还不能够保证所有节点的状态机能够按顺序执行命令。raft 对选主做出了限制，从而实现算法的正确性。</p>
<p>总的来说，这个限制只有一句话：<strong>只有保存了最新日志的节点才能选举成为 leader</strong>，选举的时候如果节点发现候选节点日志没有自己的新，则拒绝投票给它。因为保存了最新日志，因此新 leader 产生之后，follower 节点和它保持同步就不会出现数据冲突的问题。这样也能保证 leader 节点不会覆盖日志中的记录。</p>
<p>上面<strong>最新日志</strong>指的是保存了所有的已提交日志记录，因为已提交已经包含了集群中大多数节点都会有对应的日志记录，因此能保证没有最新记录的候选人选不上（因为大多数节点会拒绝投票给它），而且至少有一个节点符合条件（只要集群节点数超过 3）。</p>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>除了上述最核心的内容之外，raft 算法还有节点增删时候保证数据一致性的解决方案，以及利用快照（snapshot）进行日志压缩（log compaction）的内容，而且还要求客户端发送请求时带有一个 id，raft 集群保证请求处理的幂等性。</p>
<p>总的来说，易懂性是 raft 强调的核心，在不损失功能和性能的情况下，保证算法和系统的容易理解非常重要，这也是为什么相比很早就就出现的 paxos 算法，2013 年刚出现的 raft 就成为了很多新的分布式系统核心算法（比如分布式键值数据库 etcd ）。</p>
<h2 id="参考资料"><a href="#参考资料" class="headerlink" title="参考资料"></a>参考资料</h2><ul>
<li><a href="https://ramcloud.stanford.edu/raft.pdf" target="_blank" rel="noopener">raft 算法论文</a></li>
<li><a href="https://raft.github.io/" target="_blank" rel="noopener">raft 算法图解</a></li>
<li><a href="https://www.cnblogs.com/mindwind/p/5231986.html" target="_blank" rel="noopener">Raft 为什么是更易理解的分布式一致性算法</a></li>
<li><a href="http://thesecretlivesofdata.com/raft/" target="_blank" rel="noopener">raft 算法动画解析</a></li>
</ul>

                </div>
            </section>
        </article>
    </div>
    
<nav class="pagination">
    
    
    <a class="prev-post" title="CNCF 云原生容器生态系统概要" href="/2017/12/30/cncf-cloud-native-landscape/">
        ← CNCF 云原生容器生态系统概要
    </a>
    
    <span class="prev-next-post">•</span>
    
    <a class="next-post" title="etcd go 语言 v2 客户端开发介绍" href="/2017/12/03/etcd-v2-go-client/">
        etcd go 语言 v2 客户端开发介绍 →
    </a>
    
    
</nav>

    <div class="inner">
    <!-- Begin Mailchimp Signup Form -->
    <link href="//cdn-images.mailchimp.com/embedcode/classic-10_7.css" rel="stylesheet" type="text/css">
    <style type="text/css">
    	#mc_embed_signup{background:#fff; clear:left; font:14px Helvetica,Arial,sans-serif; }
    	/* Add your own Mailchimp form style overrides in your site stylesheet or in this style block.
    	   We recommend moving this block and the preceding CSS link to the HEAD of your HTML file. */
    </style>
    <div id="mc_embed_signup">
    <form action="https://cizixs.us7.list-manage.com/subscribe/post?u=2d561b8dea52d73a2e05e6dcb&amp;id=5c710f135b" method="post" id="mc-embedded-subscribe-form" name="mc-embedded-subscribe-form" class="validate" target="_blank" novalidate>
        <div id="mc_embed_signup_scroll">
    	<h2>订阅本博客，第一时间收到文章更新</h2>
    <div class="indicates-required"><span class="asterisk">*</span> indicates required</div>
    <div class="mc-field-group">
    	<label for="mce-EMAIL">邮件地址  <span class="asterisk">*</span>
    </label>
    	<input type="email" value="" name="EMAIL" class="required email" id="mce-EMAIL">
    </div>
    	<div id="mce-responses" class="clear">
    		<div class="response" id="mce-error-response" style="display:none"></div>
    		<div class="response" id="mce-success-response" style="display:none"></div>
    	</div>    <!-- real people should not fill this in and expect good things - do not remove this or risk form bot signups-->
        <div style="position: absolute; left: -5000px;" aria-hidden="true"><input type="text" name="b_2d561b8dea52d73a2e05e6dcb_5c710f135b" tabindex="-1" value=""></div>
        <div class="clear"><input type="submit" value="Subscribe" name="subscribe" id="mc-embedded-subscribe" class="button"></div>
        </div>
    </form>
    </div>
    <script type='text/javascript' src='//s3.amazonaws.com/downloads.mailchimp.com/js/mc-validate.js'></script><script type='text/javascript'>(function($) {window.fnames = new Array(); window.ftypes = new Array();fnames[0]='EMAIL';ftypes[0]='email';}(jQuery));var $mcj = jQuery.noConflict(true);</script>
    <!--End mc_embed_signup-->
    </div>

    <div class="inner">
        <div id="disqus_thread"></div>
    </div>

    
</main>

<div class="t-g-control">
    <div class="gotop">
        <svg class="icon" width="32px" height="32px" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg"><path d="M793.024 710.272a32 32 0 1 0 45.952-44.544l-310.304-320a32 32 0 0 0-46.4 0.48l-297.696 320a32 32 0 0 0 46.848 43.584l274.752-295.328 286.848 295.808z" fill="#8a8a8a" /></svg>
    </div>
    <div class="toc-control">
        <svg class="icon toc-icon" width="32px" height="32.00px" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg"><path d="M779.776 480h-387.2a32 32 0 0 0 0 64h387.2a32 32 0 0 0 0-64M779.776 672h-387.2a32 32 0 0 0 0 64h387.2a32 32 0 0 0 0-64M256 288a32 32 0 1 0 0 64 32 32 0 0 0 0-64M392.576 352h387.2a32 32 0 0 0 0-64h-387.2a32 32 0 0 0 0 64M256 480a32 32 0 1 0 0 64 32 32 0 0 0 0-64M256 672a32 32 0 1 0 0 64 32 32 0 0 0 0-64" fill="#8a8a8a" /></svg>
        <svg class="icon toc-close" style="display: none;" width="32px" height="32.00px" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg"><path d="M512 960c-247.039484 0-448-200.960516-448-448S264.960516 64 512 64 960 264.960516 960 512 759.039484 960 512 960zM512 128.287273c-211.584464 0-383.712727 172.128262-383.712727 383.712727 0 211.551781 172.128262 383.712727 383.712727 383.712727 211.551781 0 383.712727-172.159226 383.712727-383.712727C895.712727 300.415536 723.551781 128.287273 512 128.287273z" fill="#8a8a8a" /><path d="M557.05545 513.376159l138.367639-136.864185c12.576374-12.416396 12.672705-32.671738 0.25631-45.248112s-32.704421-12.672705-45.248112-0.25631l-138.560301 137.024163-136.447897-136.864185c-12.512727-12.512727-32.735385-12.576374-45.248112-0.063647-12.512727 12.480043-12.54369 32.735385-0.063647 45.248112l136.255235 136.671523-137.376804 135.904314c-12.576374 12.447359-12.672705 32.671738-0.25631 45.248112 6.271845 6.335493 14.496116 9.504099 22.751351 9.504099 8.12794 0 16.25588-3.103239 22.496761-9.247789l137.567746-136.064292 138.687596 139.136568c6.240882 6.271845 14.432469 9.407768 22.65674 9.407768 8.191587 0 16.352211-3.135923 22.591372-9.34412 12.512727-12.480043 12.54369-32.704421 0.063647-45.248112L557.05545 513.376159z" fill="#8a8a8a" /></svg>
    </div>
    <div class="gobottom">
        <svg class="icon" width="32px" height="32.00px" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg"><path d="M231.424 346.208a32 32 0 0 0-46.848 43.584l297.696 320a32 32 0 0 0 46.4 0.48l310.304-320a32 32 0 1 0-45.952-44.544l-286.848 295.808-274.752-295.36z" fill="#8a8a8a" /></svg>
    </div>
</div>
<div class="toc-main" style="right: -100%">
    <div class="post-toc">
        <span>TOC</span>
        <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#分布式系统和一致性"><span class="toc-text">分布式系统和一致性</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#raft-算法"><span class="toc-text">raft 算法</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#选主-leader-election"><span class="toc-text">选主 leader election</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#日志复制-Log-replication"><span class="toc-text">日志复制 Log replication</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#安全-safety"><span class="toc-text">安全 safety</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#总结"><span class="toc-text">总结</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#参考资料"><span class="toc-text">参考资料</span></a></li></ol>
    </div>
</div>



        

<aside class="read-next outer">
    <div class="inner">
        <div class="read-next-feed">
            
            

<article class="read-next-card"  style="background-image: url(https://cizixs-blog.oss-cn-beijing.aliyuncs.com/006tNc79ly1g1qxcn9ft3j318w0txdo6.jpg)"  >
  <header class="read-next-card-header">
    <small class="read-next-card-header-sitetitle">&mdash; Cizixs Write Here &mdash;</small>
    <h3 class="read-next-card-header-title">Recent Posts</h3>
  </header>
  <div class="read-next-divider">
    <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24">
      <path d="M13 14.5s2 3 5 3 5.5-2.463 5.5-5.5S21 6.5 18 6.5c-5 0-7 11-12 11C2.962 17.5.5 15.037.5 12S3 6.5 6 6.5s4.5 3.5 4.5 3.5"/>
    </svg>
  </div>
  <div class="read-next-card-content">
    <ul>
      
      
      
      <li>
        <a href="/2018/08/26/what-is-istio/">什么是 istio</a>
      </li>
      
      
      
      <li>
        <a href="/2018/08/25/knative-serverless-platform/">serverless 平台 knative 简介</a>
      </li>
      
      
      
      <li>
        <a href="/2018/06/25/kubernetes-resource-management/">kubernetes 资源管理概述</a>
      </li>
      
      
      
      <li>
        <a href="/2018/01/24/use-prometheus-and-grafana-to-monitor-linux-machine/">使用 promethues 和 grafana 监控自己的 linux 机器</a>
      </li>
      
      
      
      <li>
        <a href="/2018/01/13/linux-udp-packet-drop-debug/">linux 系统 UDP 丢包问题分析思路</a>
      </li>
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    </ul>
  </div>
  <footer class="read-next-card-footer">
    <a href="/archives">  MORE  → </a>
  </footer>
</article>


            
            
            
        </div>
    </div>
</aside>


<footer class="site-footer outer">

	<div class="site-footer-content inner">
		<section class="copyright">
			<a href="/" title="Cizixs Write Here">Cizixs Write Here</a>
			&copy; 2019
		</section>
		<nav class="site-footer-nav">
			
            <a href="https://hexo.io" title="Hexo" target="_blank" rel="noopener">Hexo</a>
            <a href="https://github.com/xzhih/hexo-theme-casper" title="Casper" target="_blank" rel="noopener">Casper</a>
        </nav>
    </div>
</footer>






<div class="floating-header" >
	<div class="floating-header-logo">
        <a href="/" title="Cizixs Write Here">
			
                <img src="https://cizixs-blog.oss-cn-beijing.aliyuncs.com/006tNc79ly1g1qxfovpzyj30740743yg.jpg" alt="Cizixs Write Here icon" />
			
            <span>Cizixs Write Here</span>
        </a>
    </div>
    <span class="floating-header-divider">&mdash;</span>
    <div class="floating-header-title">raft 一致性算法</div>
    <progress class="progress" value="0">
        <div class="progress-container">
            <span class="progress-bar"></span>
        </div>
    </progress>
</div>
<script>
   $(document).ready(function () {
    var progressBar = document.querySelector('progress');
    var header = document.querySelector('.floating-header');
    var title = document.querySelector('.post-full-title');
    var lastScrollY = window.scrollY;
    var lastWindowHeight = window.innerHeight;
    var lastDocumentHeight = $(document).height();
    var ticking = false;

    function onScroll() {
        lastScrollY = window.scrollY;
        requestTick();
    }
    function requestTick() {
        if (!ticking) {
            requestAnimationFrame(update);
        }
        ticking = true;
    }
    function update() {
        var rect = title.getBoundingClientRect();
        var trigger = rect.top + window.scrollY;
        var triggerOffset = title.offsetHeight + 35;
        var progressMax = lastDocumentHeight - lastWindowHeight;
            // show/hide floating header
            if (lastScrollY >= trigger + triggerOffset) {
                header.classList.add('floating-active');
            } else {
                header.classList.remove('floating-active');
            }
            progressBar.setAttribute('max', progressMax);
            progressBar.setAttribute('value', lastScrollY);
            ticking = false;
        }

        window.addEventListener('scroll', onScroll, {passive: true});
        update();

        // TOC
        var width = $('.toc-main').width();
        $('.toc-control').click(function () {
            if ($('.t-g-control').css('width')=="50px") {
                if ($('.t-g-control').css('right')=="0px") {
                    $('.t-g-control').animate({right: width}, "slow");
                    $('.toc-main').animate({right: 0}, "slow");
                    toc_icon()
                } else {
                    $('.t-g-control').animate({right: 0}, "slow");
                    $('.toc-main').animate({right: -width}, "slow");
                    toc_icon()
                }
            } else {
                if ($('.toc-main').css('right')=="0px") {
                    $('.toc-main').slideToggle("fast", toc_icon());
                } else {
                    $('.toc-main').css('right', '0px');
                    toc_icon()
                }
            }
        })

        function toc_icon() {
            if ($('.toc-icon').css('display')=="none") {
                $('.toc-close').hide();
                $('.toc-icon').show();
            } else {
                $('.toc-icon').hide();
                $('.toc-close').show();
            }
        }

        $('.gotop').click(function(){
            $('html,body').animate({scrollTop:$('.post-full-header').offset().top}, 800);
        });
        $('.gobottom').click(function () {
            $('html,body').animate({scrollTop:$('.pagination').offset().top}, 800);
        });

        // highlight
        // https://highlightjs.org
        $('pre code').each(function(i, block) {
            hljs.highlightBlock(block);
        });
        $('td.code').each(function(i, block) {
            hljs.highlightBlock(block);
        });

        console.log("this theme is from https://github.com/xzhih/hexo-theme-casper")
    });
</script>



<link rel="stylesheet" href="https://cdn.staticfile.org/lightgallery/1.3.9/css/lightgallery.min.css">



<script src="https://cdn.staticfile.org/lightgallery/1.3.9/js/lightgallery.min.js"></script>


<script>
	$(function () {
		var postImg = $('#lightgallery').find('img');
		postImg.addClass('post-img');
		postImg.each(function () {
			var imgSrc = $(this).attr('src');
			$(this).attr('data-src', imgSrc);
		});
		$('#lightgallery').lightGallery({selector: '.post-img'});
	});
</script>



<script>

/**
*  RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS.
*  LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/

var disqus_config = function () {
this.page.url = 'http://cizixs.com/2017/12/04/raft-consensus-algorithm/';  // Replace PAGE_URL with your page's canonical URL variable
this.page.identifier = 'http://cizixs.com/2017/12/04/raft-consensus-algorithm/'; // Replace PAGE_IDENTIFIER with your page's unique identifier variable
};

(function() { // DON'T EDIT BELOW THIS LINE
var d = document, s = d.createElement('script');
s.src = 'https://cizixs.disqus.com/embed.js';
s.setAttribute('data-timestamp', +new Date());
(d.head || d.body).appendChild(s);
})();
</script>
<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
                            


    </div>
</body>
</html>
